// 路径总和 I
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;
        if (root->left == nullptr && root->right == nullptr) 
        {
            return targetSum == root->val;
        }
        return hasPathSum(root->left, targetSum - root->val) 
            || hasPathSum(root->right, targetSum - root->val);
    }
};

// 路径总和 II
class Solution {
    vector<vector<int>> res;
    vector<int> path;
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }
    void dfs(TreeNode* root, int t)
    {
        if (root == nullptr) return;
        path.push_back(root->val);
        if (root->left == nullptr && root->right == nullptr && t == root->val)
        {
            res.push_back(path);
        }
        dfs(root->left, t - root->val);
        dfs(root->right, t - root->val);
        path.pop_back(); // 回溯
    }
};

// 路径总和 III
class Solution {
    using ll = long long;
    unordered_map<ll, int> pre_cnt; // 记录前缀和及其出现次数
    int t;
public:
    int pathSum(TreeNode* root, int targetSum) {
        t = targetSum;
        pre_cnt[0] = 1; // 前缀和恰好等于目标值
        return dfs(root, 0);
    }
    int dfs(TreeNode* root, ll sum) {
        if (root == nullptr) return 0;
        sum += root->val;
        int count = pre_cnt[sum - t];
        pre_cnt[sum]++;
        count += dfs(root->left, sum);
        count += dfs(root->right, sum);
        pre_cnt[sum]--;
        return count;
    }
};
